{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Initial Energy to Finish Tasks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumEffort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完成所有任务的最少初始能量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个任务数组 <code>tasks</code> ，其中 <code>tasks[i] = [actual<sub>i</sub>, minimum<sub>i</sub>]</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>actual<sub>i</sub></code> 是完成第 <code>i</code> 个任务 <strong>需要耗费</strong> 的实际能量。</li>\n",
    "\t<li><code>minimum<sub>i</sub></code> 是开始第 <code>i</code> 个任务前需要达到的最低能量。</li>\n",
    "</ul>\n",
    "\n",
    "<p>比方说，如果任务为 <code>[10, 12]</code> 且你当前的能量为 <code>11</code> ，那么你不能开始这个任务。如果你当前的能量为 <code>13</code> ，你可以完成这个任务，且完成它后剩余能量为 <code>3</code> 。</p>\n",
    "\n",
    "<p>你可以按照 <strong>任意顺序</strong> 完成任务。</p>\n",
    "\n",
    "<p>请你返回完成所有任务的 <strong>最少</strong> 初始能量。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [[1,2],[2,4],[4,8]]\n",
    "<b>输出：</b>8\n",
    "<strong>解释：</strong>\n",
    "一开始有 8 能量，我们按照如下顺序完成任务：\n",
    "    - 完成第 3 个任务，剩余能量为 8 - 4 = 4 。\n",
    "    - 完成第 2 个任务，剩余能量为 4 - 2 = 2 。\n",
    "    - 完成第 1 个任务，剩余能量为 2 - 1 = 1 。\n",
    "注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]\n",
    "<b>输出：</b>32\n",
    "<strong>解释：</strong>\n",
    "一开始有 32 能量，我们按照如下顺序完成任务：\n",
    "    - 完成第 1 个任务，剩余能量为 32 - 1 = 31 。\n",
    "    - 完成第 2 个任务，剩余能量为 31 - 2 = 29 。\n",
    "    - 完成第 3 个任务，剩余能量为 29 - 10 = 19 。\n",
    "    - 完成第 4 个任务，剩余能量为 19 - 10 = 9 。\n",
    "    - 完成第 5 个任务，剩余能量为 9 - 8 = 1 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]\n",
    "<b>输出：</b>27\n",
    "<strong>解释：</strong>\n",
    "一开始有 27 能量，我们按照如下顺序完成任务：\n",
    "    - 完成第 5 个任务，剩余能量为 27 - 5 = 22 。\n",
    "    - 完成第 2 个任务，剩余能量为 22 - 2 = 20 。\n",
    "    - 完成第 3 个任务，剩余能量为 20 - 3 = 17 。\n",
    "    - 完成第 1 个任务，剩余能量为 17 - 1 = 16 。\n",
    "    - 完成第 4 个任务，剩余能量为 16 - 4 = 12 。\n",
    "    - 完成第 6 个任务，剩余能量为 12 - 6 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= tasks.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= actual<sub>​i</sub> &lt;= minimum<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-initial-energy-to-finish-tasks](https://leetcode.cn/problems/minimum-initial-energy-to-finish-tasks/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-initial-energy-to-finish-tasks](https://leetcode.cn/problems/minimum-initial-energy-to-finish-tasks/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,4],[4,8]]', '[[1,3],[2,4],[10,11],[10,12],[8,9]]', '[[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x:x[1] - x[0]) #根据剩余能量升序排列\n",
    "        res = 0#需要的初始能量\n",
    "        t = 0#当前能量\n",
    "        while tasks:\n",
    "            i, j = tasks.pop()#从尾部弹出即是降序\n",
    "            if t < j:#如果当前能量小于最低能量，补齐至最低能量\n",
    "                res += j - t\n",
    "                t = j - i\n",
    "            else:\n",
    "                t -= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x:x[1] - x[0]) #根据剩余能量升序排列\n",
    "        res = 0#需要的初始能量\n",
    "        t = 0#当前能量\n",
    "        while tasks:\n",
    "            i, j = tasks.pop()#从尾部弹出即是降序\n",
    "            if t < j:#如果当前能量小于最低能量，补齐至最低能量\n",
    "                res += j - t\n",
    "                t = j - i\n",
    "            else:\n",
    "                t -= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#使用二分只能过一半，因为这种顺序不对\n",
    "# class Solution:\n",
    "#     def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "#         tasks.sort(key=lambda x:(-x[-1],x[0]))\n",
    "#         left = tasks[0][1]\n",
    "#         right = left+(sum(tasks[i][0] for i in range(len(tasks))))\n",
    "#         while left < right:\n",
    "#             mid = left+(right-left)//2\n",
    "#             if self.manzu(mid,tasks):\n",
    "#                 right = mid\n",
    "#             else:\n",
    "#                 left = mid+1\n",
    "#         return left\n",
    "#     def manzu(self,mid,tasks):\n",
    "#         for i in range(len(tasks)):\n",
    "#             if tasks[i][1]<=mid:\n",
    "#                 mid = mid-tasks[i][0]\n",
    "#             else:\n",
    "#                 return False\n",
    "#         return True\n",
    "\n",
    "#贪心\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x:x[1] - x[0]) #根据剩余能量升序排列\n",
    "        res = 0#需要的初始能量\n",
    "        t = 0#当前能量\n",
    "        while tasks:\n",
    "            i, j = tasks.pop()#从尾部弹出即是降序\n",
    "            if t < j:#如果当前能量小于最低能量，补齐至最低能量\n",
    "                res += j - t\n",
    "                t = j - i\n",
    "            else:\n",
    "                t -= i\n",
    "        return res\n",
    "# 初始能量 = 消耗能量总和 + 剩余能量 一定是成立的。 可以得知消耗能量总和是不变的，也就是说初始能量最小时就是剩余能量最小时。 需要寻找最小剩余能量则只需要将每个任务的剩余能量降序排列依次遍历即可求解。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x:x[1] - x[0])\n",
    "        res = 0\n",
    "        t = 0\n",
    "        while tasks:\n",
    "            i, j = tasks.pop()\n",
    "            if t < j:\n",
    "                res += j - t\n",
    "                t = j - i\n",
    "            else:\n",
    "                t -= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks):\n",
    "        tasks.sort(key = lambda x:x[1]-x[0])\n",
    "        res = 0\n",
    "        t = 0\n",
    "        while tasks:\n",
    "            i, j = tasks.pop()\n",
    "            if t < j:\n",
    "                res += j - t\n",
    "                t = j - i\n",
    "            else:\n",
    "                t -= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x:x[1] - x[0]) #根据剩余能量升序排列\n",
    "        res = 0#需要的初始能量\n",
    "        t = 0#当前能量\n",
    "        while tasks:\n",
    "            i, j = tasks.pop()#从尾部弹出即是降序\n",
    "            if t < j:#如果当前能量小于最低能量，补齐至最低能量\n",
    "                res += j - t\n",
    "                t = j - i\n",
    "            else:\n",
    "                t -= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x:x[1] - x[0]) #根据剩余能量升序排列\n",
    "        res = 0#需要的初始能量\n",
    "        t = 0#当前能量\n",
    "        while tasks:\n",
    "            i, j = tasks.pop()#从尾部弹出即是降序\n",
    "            if t < j:#如果当前能量小于最低能量，补齐至最低能量\n",
    "                res += j - t\n",
    "                t = j - i\n",
    "            else:\n",
    "                t -= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        n = len(tasks)\n",
    "        res = [(tasks[i][1] - tasks[i][0], i) for i in range(n)]\n",
    "        res.sort()\n",
    "        ans = res[0][0]\n",
    "        for item in res:\n",
    "            needed, idx = item[0], item[1]\n",
    "            if ans >= needed:\n",
    "                ans = ans + tasks[idx][0]\n",
    "            else:\n",
    "                ans = tasks[idx][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x: (x[0]-x[1], -x[1]))\n",
    "        def fun(energy):\n",
    "            for actual, minimum in tasks:\n",
    "                if energy < minimum:\n",
    "                    return False\n",
    "                else:\n",
    "                    energy -= actual\n",
    "            return True\n",
    "        left, right = 0, max([b for a, b in tasks])*len(tasks)\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if fun(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x:x[1]-x[0],reverse=True)\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for x in tasks:\n",
    "            if cur<x[1]:\n",
    "                ans += x[1]-cur\n",
    "                print(x[1]-cur,x[1])\n",
    "                cur = x[1]\n",
    "            cur-=x[0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x: (x[0] - x[1], -x[1], x[0]))\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for a, m in tasks:\n",
    "            if m > cur:\n",
    "                ans += (m - cur)\n",
    "                cur = m \n",
    "            cur -= a\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks = sorted(tasks,key=lambda x:x[1]-x[0])\n",
    "        res = 0\n",
    "        for energy,req in tasks:\n",
    "            res = max(res+energy,req)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for a,m in sorted(tasks,key = lambda x: x[1]-x[0]):\n",
    "            ans = max(ans+a,m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        tasks.sort(key = lambda x: x[1] - x[0])\n",
    "        print(tasks)\n",
    "        for need,limit in tasks:\n",
    "            ans += need\n",
    "            ans += max(0,limit - ans)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for a, m in sorted(tasks, key=lambda k: k[1] - k[0]):\n",
    "            ans = max(ans + a, m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks = sorted(tasks, key=lambda x: x[-1] - x[0])\n",
    "        ans = 0\n",
    "        # print(tasks)\n",
    "        for a, b in tasks:\n",
    "            ans = max(a + ans, b)\n",
    "            # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x: (x[0] - x[1]))\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for a, m in tasks:\n",
    "            if m > cur:\n",
    "                ans += (m - cur)\n",
    "                cur = m \n",
    "            cur -= a\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x: (x[1]-x[0], x[1]))\n",
    "        pre = 0\n",
    "        for a, m in tasks:\n",
    "            pre += a\n",
    "            if pre < m: pre = m\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        arr = sorted(tasks, key = lambda x:(x[0] - x[1]))\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for x,y in arr:\n",
    "            if cur < y:\n",
    "                ans += y - cur\n",
    "                cur = y\n",
    "            cur -= x\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        energy = ans = 0\n",
    "        for a, m in sorted(tasks, key=lambda x: x[0]-x[1]):\n",
    "            if energy < m:\n",
    "                ans += m - energy\n",
    "                energy = m\n",
    "            energy -= a\n",
    "        return ans\n",
    "        # 12 9 8 3 1\n",
    "        # 2 1 1 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        ret, tmp = 0 ,0\n",
    "        for (a, m) in sorted(tasks, key=lambda x: -(x[1] - x[0])):\n",
    "            if m > tmp: # 剩余能量小于最小启动能量\n",
    "                ret += m - tmp  # 增加最小能量差值\n",
    "                tmp = m # 最小启动能量\n",
    "            tmp -= a    # 剩余能量\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1] - x[0])\n",
    "        res = 0\n",
    "        for i, j in tasks:\n",
    "            res = max(res + i, j)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "\n",
    "        # 按照结束时间对任务进行排序\n",
    "        # tasks.sort(key=lambda x: x[1] - x[0])\n",
    "        tasks.sort(key=lambda x: (x[1] - x[0], x[0]))\n",
    "\n",
    "        # 初始化结果\n",
    "        result = 0\n",
    "\n",
    "        # 遍历任务，计算当前任务的最小努力值\n",
    "        for task in tasks:\n",
    "            result = max(result + task[0], task[1])\n",
    "\n",
    "        # 返回所有任务的最大努力值\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        # 排序，应该先做 min - act 更大的任务\n",
    "        cur = use = 0\n",
    "        tasks.sort(key=lambda x:(x[1] - x[0]), reverse=True)\n",
    "        for t in tasks:\n",
    "            cur += max(0, t[1]-cur)\n",
    "            cur -= t[0]\n",
    "            use += t[0]\n",
    "        return cur+use"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x:x[1]-x[0])\n",
    "        cur = 0\n",
    "        for a,b in tasks:\n",
    "            cur1 = cur+a\n",
    "            cur = cur1 if cur1>b else b\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        ts = sorted(tasks, key=lambda task: (task[0]-task[1]))\n",
    "        def check(i):\n",
    "            for (a, m) in ts:\n",
    "                # print(i, a, m)\n",
    "                if i>=m and i-a>=0:\n",
    "                    i-=a\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        l = 0\n",
    "        r = 10**9\n",
    "        while abs(r-l)>3:\n",
    "            m = (l+r)>>1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m+1\n",
    "        for i in range(l, r+1):\n",
    "            if check(i):\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1] - t[0])\n",
    "        ans = 0\n",
    "        for cost, need in tasks:\n",
    "            ans = max(ans + cost, need)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[0] - x[1])\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for a, m in tasks:\n",
    "            if cur < m:\n",
    "                ans += m - cur\n",
    "                cur = m\n",
    "            cur -= a\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1] - x[0])\n",
    "        ans = 0\n",
    "        for a, m in tasks:\n",
    "            ans = max(ans + a, m)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1]-x[0])\n",
    "        cur = 0\n",
    "        print(tasks)\n",
    "        for item in tasks:\n",
    "            if cur < item[1]-item[0]:\n",
    "                cur = item[1]-item[0]\n",
    "            cur = cur+item[0]\n",
    "            \n",
    "\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[0]-x[1])\n",
    "        res = s = 0\n",
    "        for a, m in tasks:\n",
    "            if res < s + m:\n",
    "                res = s + m\n",
    "            s += a\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        # s = maxn = 0\n",
    "        # d = inf\n",
    "        # for actual, minimum in tasks:\n",
    "        #     s += actual\n",
    "        #     maxn = max(maxn, minimum)\n",
    "        #     d = min(max(0, minimum - actual), d)\n",
    "        # return max(s + d, maxn)\n",
    "        s = ans = 0\n",
    "        tasks.sort(key=lambda x: x[0] - x[1])\n",
    "        for actual, minimum in tasks:\n",
    "            if s + minimum > ans:\n",
    "                ans = minimum + s\n",
    "            s += actual\n",
    "            if s > ans:\n",
    "                ans = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        if not tasks: return 0\n",
    "        tasks.sort(key=lambda x: (x[0]-x[1]))\n",
    "        cur_strength, min_strength = 0, 0\n",
    "\n",
    "        for consume, threshold in tasks:\n",
    "            if cur_strength < threshold:\n",
    "                min_strength += threshold - cur_strength\n",
    "                cur_strength = threshold\n",
    "            cur_strength -= consume\n",
    "        return min_strength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x:x[1]-x[0])\n",
    "        cur = 0\n",
    "        for a,b in tasks:\n",
    "            cur = cur+a if cur+a>b else b\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x:x[1]-x[0])\n",
    "        cur = 0\n",
    "        for a,b in tasks:\n",
    "            cur = cur+a if cur+a>b else b\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        cur = 0\n",
    "        use = 0\n",
    "        tasks.sort(key=lambda x:(x[1] - x[0]), reverse=True)\n",
    "        for t in tasks:\n",
    "            cur += max(0, t[1]-cur)\n",
    "            cur -= t[0]\n",
    "            use += t[0]\n",
    "        return cur+use"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        n = len(tasks)\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        tasks.sort(key = lambda x:(x[0] - x[1]))\n",
    "        for x,y in tasks:\n",
    "            if count < y:\n",
    "                ans += y - count\n",
    "                count = y\n",
    "            count -= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        ret, tmp = 0 ,0\n",
    "        for (a, m) in sorted(tasks, key=lambda x: -(x[1] - x[0])):  # 按差值大小进行排序\n",
    "            if m > tmp: # 剩余能量小于最低能量\n",
    "                ret += m - tmp  # 增加能量差值\n",
    "                tmp = m # 最低能量\n",
    "            tmp -= a    # 剩余能量\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        tasks.sort(key = lambda x: x[1] - x[0])\n",
    "        # print(tasks)\n",
    "        for need,limit in tasks:\n",
    "            ans += need\n",
    "            ans += max(0,limit - ans)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1] - x[0])\n",
    "        ans = 0\n",
    "        for cost, min_energy in tasks:\n",
    "            ans += cost\n",
    "            ans = max(ans, min_energy)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[0] - x[1])\n",
    "        result = cur = 0\n",
    "        for a, b in tasks:\n",
    "            result = max(result, cur + b)\n",
    "            cur += a\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        total=sum(task[0] for task in tasks)\n",
    "        cur=total\n",
    "        tasks.sort(key=lambda x:x[0]-x[1])\n",
    "        for i in range(len(tasks)):\n",
    "            if tasks[i][1]>cur:\n",
    "                total+=tasks[i][1]-cur\n",
    "                cur=tasks[i][1]\n",
    "            cur-=tasks[i][0]\n",
    "            # print(cur)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, mid):\n",
    "        for a, m in self.tasks:\n",
    "            if mid<m: return False\n",
    "            mid -= a\n",
    "        return True\n",
    "\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        l, r, self.tasks = 0, sum(i[1] for i in tasks), sorted(tasks, key=lambda x: x[0]-x[1])\n",
    "        while r-l>1:\n",
    "            mid = (l+r)//2\n",
    "            if self.f(mid): r = mid\n",
    "            else: l = mid\n",
    "        return l if self.f(l) else r\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x: x[1]-x[0])\n",
    "        res = 0\n",
    "        for a, m in tasks:\n",
    "            res += max(m - res, a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        n = len(tasks)\n",
    "        ans = sum(tasks[i][0] for i in range(n))\n",
    "        count = ans\n",
    "        tasks.sort(key = lambda x:(x[0] - x[1]))\n",
    "        for x,y in tasks:\n",
    "            if count < y:\n",
    "                ans += y - count\n",
    "                count = y\n",
    "            count -= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1] - x[0])\n",
    "        ans = 0\n",
    "        for a, m in tasks:\n",
    "            ans = ans + a if ans + a > m else m\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x:(x[0]-x[1]))\n",
    "        res=0\n",
    "        last=0\n",
    "\n",
    "        for a,m in tasks:\n",
    "            if last<m:\n",
    "                res+=m-last\n",
    "                last=m\n",
    "            last-=a\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[0]-x[1])\n",
    "        res = s = 0\n",
    "        for a, m in tasks:\n",
    "            if res < s + m:\n",
    "                res = s + m\n",
    "            s += a\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks = sorted(tasks, key=lambda x: x[1]-x[0])\n",
    "        a, b = tasks[0][0], tasks[0][1]\n",
    "        for i in range(1, len(tasks)):\n",
    "            b = max(min(b+tasks[i][0], a+tasks[i][1]), b, tasks[i][1])\n",
    "            a += tasks[i][0]\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x:(-x[1]+x[0]))\n",
    "        res = 0\n",
    "        v = 0\n",
    "        for actual, minimum in tasks:\n",
    "            if v < minimum:\n",
    "                diff = minimum - v\n",
    "                v += diff\n",
    "                res += diff\n",
    "            v -= actual\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1] - x[0])\n",
    "        ans = 0\n",
    "        for a, m in tasks:\n",
    "            ans = ans + a if ans + a > m else m\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x: x[1] - x[0])\n",
    "\n",
    "        ans = 0\n",
    "        for x, y in tasks:\n",
    "            if ans + x >= y:\n",
    "                ans += x\n",
    "            else:\n",
    "                ans = y\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        tasks.sort(key=lambda x:-x[1]+x[0])\n",
    "        temp=0\n",
    "        for i in range(len(tasks)):\n",
    "            if tasks[i][1]>temp:\n",
    "                ans+=tasks[i][1]-temp\n",
    "                temp=tasks[i][1]-tasks[i][0]\n",
    "            else:\n",
    "                temp-=tasks[i][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        need, e = 0, 0\n",
    "        tasks.sort(key=lambda x: (x[0]-x[1], -x[1]))\n",
    "        for a, m in tasks:\n",
    "            if m>e:\n",
    "                need += m-e\n",
    "                e = m\n",
    "            e -= a\n",
    "        return need \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1] - x[0])\n",
    "        res = 0\n",
    "        for task in tasks:\n",
    "            res = max(res + task[0], task[1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        '''tasks.sort(key = lambda x:(x[1]-x[0],x[1]))\n",
    "        return sum([i[0] for i in tasks]) + tasks[-1][1]-tasks[-1][0]'''\n",
    "        tasks.sort(key = lambda x:x[0]-x[1])\n",
    "        ans = 0\n",
    "        res = 0\n",
    "        for i in tasks:\n",
    "            if ans >= i[1]:\n",
    "                ans -= i[0]\n",
    "            else:\n",
    "                \n",
    "                res += i[1]-ans\n",
    "                ans = i[1]-i[0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[0] - t[1])\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        for actual, minimum in tasks:\n",
    "            if s < minimum:\n",
    "                ans += minimum - s\n",
    "                s = minimum\n",
    "            s -= actual\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1]-x[0])\n",
    "        cur = 0\n",
    "        print(tasks)\n",
    "        for item in tasks:\n",
    "            if cur < item[1]-item[0]:\n",
    "                cur = item[1]-item[0]\n",
    "            cur = cur+item[0]\n",
    "            \n",
    "\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key = lambda x: -(x[1] - x[0]))\n",
    "        print(tasks)\n",
    "\n",
    "        l, r = tasks[0][1], sum(item[1] for item in tasks)\n",
    "        # print('l, r: ', l, r)\n",
    "        def check(c: int) -> bool:\n",
    "            startC = c\n",
    "            for task in tasks:\n",
    "                if startC < task[1]: return False\n",
    "                startC -= task[0]\n",
    "            return True\n",
    "\n",
    "\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            \n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1] - x[0])\n",
    "        print(tasks)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for x, y in tasks:\n",
    "            ans += x\n",
    "            if ans < y:\n",
    "                ans = y\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks):\n",
    "        # 按照 actuali - minimumi 排序\n",
    "        tasks.sort(key=lambda x: (x[0]-x[1], x[1]))\n",
    "        \n",
    "        # 初始化能量为 0\n",
    "        energy = 0\n",
    "        curr_energy = 0\n",
    "\n",
    "        for actual, minimum in tasks:\n",
    "            # 如果当前能量不足以开始任务，则需要补充能量\n",
    "            if curr_energy < minimum:\n",
    "                # 计算需要补充的能量\n",
    "                diff = minimum - curr_energy\n",
    "                energy += diff\n",
    "                curr_energy += diff\n",
    "            # 完成任务后更新能量\n",
    "            curr_energy -= actual\n",
    "\n",
    "        return energy\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, brr: List[List[int]]) -> int:\n",
    "        brr.sort(key = lambda x : x[0]-x[1])\n",
    "\n",
    "        # 不能超过4800\n",
    "        l, r = 0, 10**9\n",
    "        while l < r:\n",
    "            mid = l+r>>1\n",
    "            flag = True\n",
    "            t = mid\n",
    "            for a, b in brr:\n",
    "                if t < b:\n",
    "                    flag = False\n",
    "                else:\n",
    "                    t -= a\n",
    "            if flag:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        # nums = [list(map(int,x.split(':'))) for x in input().split(',')]\n",
    "        nums = tasks\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "\n",
    "\n",
    "        nums.sort(key=lambda x:(x[0]-x[1]))\n",
    "\n",
    "        p ,s = 0,0\n",
    "        for i in range(len(nums)):\n",
    "            p = max(p,s+nums[i][1])\n",
    "            s += nums[i][0]\n",
    "        # if p>4800:\n",
    "        #     return -1\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumEffort(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: -(x[1] - x[0]))\n",
    "        n = len(tasks)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x = tasks[i]\n",
    "            if ans + x[0] >= x[1]:\n",
    "                ans += x[0]\n",
    "            else:\n",
    "                ans = x[1]\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
